<HTML><HEAD><TITLE>library(graph_algorithms)</TITLE></HEAD><BODY>
[ <A HREF="../../index.html">Reference Manual</A> | <A HREF="../../fullindex.html">Alphabetic Index</A> ]<H1>library(graph_algorithms)</H1>
Collection of graph algorithms
<H2>Predicates</H2>
<BLOCKQUOTE>
<DL>
<DT><A HREF="all_short_paths_as_edges-6.html"><STRONG>all_short_paths_as_edges(+Graph, +DistanceArg, +SourceNode, +Tolerance, -Lengths, -Predecessors)</STRONG></A></DT>
<DD>Computes all shortest paths from a single source to every reachable node</DD>
<DT><A HREF="all_short_paths_as_graph-6.html"><STRONG>all_short_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +Tolerance, -Lengths, -SubGraph)</STRONG></A></DT>
<DD>Computes all shortest paths from a single source in form of a subgraph</DD>
<DT><A HREF="articulation_points-2.html"><STRONG>articulation_points(+Graph, -Articulations)</STRONG></A></DT>
<DD>Finds the articulation points of the graph</DD>
<DT><A HREF="biconnected_components-3.html"><STRONG>biconnected_components(+Graph, -Articulations, -BCC)</STRONG></A></DT>
<DD>Finds the biconnected components of the graph</DD>
<DT><A HREF="connected_components-2.html"><STRONG>connected_components(+Graph, -ConnectedComponents)</STRONG></A></DT>
<DD>Computes the connected components of graph</DD>
<DT><A HREF="critical_links-2.html"><STRONG>critical_links(+Graph, -Links)</STRONG></A></DT>
<DD>Finds critical links in a bidirected graph</DD>
<DT><A HREF="graph_adjacent_edge-3.html"><STRONG>graph_adjacent_edge(+Graph, +Node, ?Edge)</STRONG></A></DT>
<DD>Succeeds if Edge is an edge adjacent to Node in Graph</DD>
<DT><A HREF="graph_cycles-2.html"><STRONG>graph_cycles(+Graph, -BreakingEdges)</STRONG></A></DT>
<DD>Computes a list of edges whose removal would make the graph acyclic</DD>
<DT><A HREF="graph_edge-2.html"><STRONG>graph_edge(+Graph, ?Edge)</STRONG></A></DT>
<DD>Succeeds if Edge is an edge in graph</DD>
<DT><A HREF="graph_get_adjacent_edges-3.html"><STRONG>graph_get_adjacent_edges(+Graph, +SourceNode, -EdgeList)</STRONG></A></DT>
<DD>Returns a sorted list of all edges starting from SourceNode</DD>
<DT><A HREF="graph_get_all_edges-2.html"><STRONG>graph_get_all_edges(+Graph, -EdgeList)</STRONG></A></DT>
<DD>Returns a sorted list of all edges in the graph</DD>
<DT><A HREF="graph_get_edge-4.html"><STRONG>graph_get_edge(+Graph, +Source, +Target, -Edge)</STRONG></A></DT>
<DD>Finds a graph edge given source and target node</DD>
<DT><A HREF="graph_get_edges-4.html"><STRONG>graph_get_edges(+Graph, +Source, +Target, -Edges)</STRONG></A></DT>
<DD>Finds all edges between source node and target node</DD>
<DT><A HREF="graph_get_incoming_edges-3.html"><STRONG>graph_get_incoming_edges(+Graph, +TargetNode, -EdgeList)</STRONG></A></DT>
<DD>Returns a sorted list of all edges ending in TargetNode</DD>
<DT><A HREF="graph_get_maxnode-2.html"><STRONG>graph_get_maxnode(+Graph, -MaxNode)</STRONG></A></DT>
<DD>Returns the highest node number in Graph</DD>
<DT><A HREF="graph_get_nodenames-2.html"><STRONG>graph_get_nodenames(+Graph, -NodeNameArray)</STRONG></A></DT>
<DD>Returns the array of node names</DD>
<DT><A HREF="graph_is_acyclic-1.html"><STRONG>graph_is_acyclic(+Graph)</STRONG></A></DT>
<DD>Succeeds iff the given graph has no cycles</DD>
<DT><A HREF="graph_is_bidirected-1.html"><STRONG>graph_is_bidirected(+Graph)</STRONG></A></DT>
<DD>Tests whether a graph is bidirected</DD>
<DT><A HREF="graph_node-2.html"><STRONG>graph_node(+Graph, ?Node)</STRONG></A></DT>
<DD>Succeeds if Node is a node of the graph</DD>
<DT><A HREF="graph_reverse_edges-2.html"><STRONG>graph_reverse_edges(+Graph, -RevGraph)</STRONG></A></DT>
<DD>Makes a graph with reversed edges</DD>
<DT><A HREF="graph_set_nodenames-2.html"><STRONG>graph_set_nodenames(+Graph, ++NodeNameArray)</STRONG></A></DT>
<DD>Add node names to an existing graph</DD>
<DT><A HREF="graph_set_random_weights-3.html"><STRONG>graph_set_random_weights(+Graph, +Min, +Max)</STRONG></A></DT>
<DD>Unifies all the graph's edge data fields with random numbers</DD>
<DT><A HREF="incremental_all_shortest_paths_as_edges-6.html"><STRONG>incremental_all_shortest_paths_as_edges(+Graph, +DistanceArg, +SourceNode, +Modified, -Lengths, -Predecessors)</STRONG></A></DT>
<DD>Incrementally computes all shortest paths from a single source to every reachable node given a list of modified edges</DD>
<DT><A HREF="incremental_all_shortest_paths_as_graph-6.html"><STRONG>incremental_all_shortest_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +Modified, -Lengths, -SubGraph)</STRONG></A></DT>
<DD>Incrementally computes all shortest paths from a single source to every reachable node given a list of modified edges</DD>
<DT><A HREF="incremental_single_pair_all_shortest_paths_as_graph-7.html"><STRONG>incremental_single_pair_all_shortest_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Modified, -Length, -SubGraph)</STRONG></A></DT>
<DD>Computes all shortest paths from source to sink in form of a subgraph</DD>
<DT><A HREF="incremental_single_pair_shortest_path-6.html"><STRONG>incremental_single_pair_shortest_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Modified, -Path)</STRONG></A></DT>
<DD>Computes short paths from a source to a sink node</DD>
<DT><A HREF="is_sub_graph-2.html"><STRONG>is_sub_graph(+SubGraph, +SuperGraph)</STRONG></A></DT>
<DD>Succeeds iff SubGraph is a subgraph of SuperGraph</DD>
<DT><A HREF="make_graph-3.html"><STRONG>make_graph(+NNodes, ++EdgeList, -Graph)</STRONG></A></DT>
<DD>Creates a graph with minimal overhead</DD>
<DT><A HREF="make_graph_symbolic-3.html"><STRONG>make_graph_symbolic(+NodeNameArray, ++SymbolicEdgeList, -Graph)</STRONG></A></DT>
<DD>Creates a graph using node names</DD>
<DT><A HREF="make_random_graph-6.html"><STRONG>make_random_graph(+NNodes, +NEdges, +AntiParallelFree, +LoopFree, +ParallelFree, -Graph)</STRONG></A></DT>
<DD>Creates a random graph with the given properties</DD>
<DT><A HREF="make_sub_graph-3.html"><STRONG>make_sub_graph(+Graph, ++Nodes, -SubGraph)</STRONG></A></DT>
<DD>Creates a subgraph (projection on nodes) of a given graph</DD>
<DT><A HREF="make_undirected_graph-2.html"><STRONG>make_undirected_graph(+DirectedGraph, -UndirectedGraph)</STRONG></A></DT>
<DD>Creates an undirected from a directed graph</DD>
<DT><A HREF="maximum_matching_hopcroft_karp-4.html"><STRONG>maximum_matching_hopcroft_karp(+G, ++A, ++B, -MaximalM)</STRONG></A></DT>
<DD>Compute the maximum matching in a bipartite graph using Hopcroft and Karp's algorithm</DD>
<DT><A HREF="minimum_spanning_forest-5.html"><STRONG>minimum_spanning_forest(+Graph, +DistanceArg, -Forest, -ForestSize, -ForestWeight)</STRONG></A></DT>
<DD>Computes a minimum spanning forest, its size and weight</DD>
<DT><A HREF="minimum_spanning_tree-4.html"><STRONG>minimum_spanning_tree(+Graph, +DistanceArg, -Tree, -TreeWeight)</STRONG></A></DT>
<DD>Computes a minimum spanning tree and its weight</DD>
<DT><A HREF="node_to_nodename-3.html"><STRONG>node_to_nodename(+Graph, +Node, -NodeName)</STRONG></A></DT>
<DD>Retrieves the name of a node</DD>
<DT><A HREF="nodename_to_node-3.html"><STRONG>nodename_to_node(+Graph, +NodeName, -Node)</STRONG></A></DT>
<DD>Retrieves the node number given a node name</DD>
<DT><A HREF="nodenames_to_nodes-3.html"><STRONG>nodenames_to_nodes(+Graph, +NodeNames, -Nodes)</STRONG></A></DT>
<DD>Returns the names corresponding to a list of nodes</DD>
<DT><A HREF="nodes_to_nodenames-3.html"><STRONG>nodes_to_nodenames(+Graph, +Nodes, -NodeNames)</STRONG></A></DT>
<DD>Returns the names corresponding to a list of nodes</DD>
<DT><A HREF="possible_path-6.html"><STRONG>possible_path(+SourceNode, +SinkNode, +Tolerance, +Lengths, +Predecessors, -Path)</STRONG></A></DT>
<DD>Computes an actual path from a predecessors array</DD>
<DT><A HREF="possible_path-7.html"><STRONG>possible_path(+DistanceArg, +SourceNode, +SinkNode, +Tolerance, +Lengths, +Predecessors, -Path)</STRONG></A></DT>
<DD>Computes an actual path from a predecessors array</DD>
<DT><A HREF="proper_graph-1.html"><STRONG>proper_graph(+Graph)</STRONG></A></DT>
<DD>Tests the integrity of the given graph data structure</DD>
<DT><A HREF="shortest_paths-4.html"><STRONG>shortest_paths(+Graph, +DistanceArg, +SourceNode, -Paths)</STRONG></A></DT>
<DD>Computes one shortest path from a single source to every reachable node</DD>
<DT><A HREF="shortest_paths_bellman_ford-4.html"><STRONG>shortest_paths_bellman_ford(+Graph, +DistanceArg, +SourceNode, -Paths)</STRONG></A></DT>
<DD>Computes one shortest path from a single source to every reachable node (allowing negative distances)</DD>
<DT><A HREF="single_pair_all_short_paths_as_graph-7.html"><STRONG>single_pair_all_short_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Tolerance, -Length, -SubGraph)</STRONG></A></DT>
<DD>Computes all shortest paths from source to sink in form of a subgraph</DD>
<DT><A HREF="single_pair_short_path-6.html"><STRONG>single_pair_short_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Tolerance, -Path)</STRONG></A></DT>
<DD>Computes short paths from a source to a sink node</DD>
<DT><A HREF="single_pair_shortest_path-5.html"><STRONG>single_pair_shortest_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, -Path)</STRONG></A></DT>
<DD>Computes one shortest path from a source to a sink node</DD>
<DT><A HREF="single_pair_shortest_path_bellman_ford-5.html"><STRONG>single_pair_shortest_path_bellman_ford(+Graph, +DistanceArg, +SourceNode, +SinkNode, -Path)</STRONG></A></DT>
<DD>Computes one shortest path from a source to a sink node (allowing negative distances)</DD>
<DT><A HREF="strong_components-2.html"><STRONG>strong_components(+Graph, -StrongComponents)</STRONG></A></DT>
<DD>Computes the strongly connected components of a graph</DD>
<DT><A HREF="top_sort-2.html"><STRONG>top_sort(+Graph, -Sorted)</STRONG></A></DT>
<DD>Finds a topological ordering of the graph if one exists</DD>
</DL>
</BLOCKQUOTE>
<H2>Description</H2>
<P>
    This library is a collection of graph algorithms.
</P><P>
    In its simplest form, a graph consists of a (possibly empty) set of
    nodes (numbered from 1 to NNodes), and zero or more directed edges
    between these nodes. An edge is represented by the data structure
<PRE>
	e(Source, Target, EdgeData)
</PRE>
    where Source and Target are integers indicating the start and end
    point of the edge, and EdgeData is an arbitrary data structure
    holding additional information about the edge, e.g. capacity,
    distance, weight, name etc.  The EdgeData field should have the
    same structure for all edges in a graph.  If there is no
    information attached to edges, the field should be set to 1
    for edges between different nodes and to 0 otherwise.
    Several library predicates inspect the EdgeData field or an argument
    of the EdgeData field, e.g. the shortest path predicate can
    use any numeric component of EdgeData as the distance criterion.
</P><P>
    The most efficient way to create a graph is to use make_graph/3
    which takes the number of nodes and a list of edges and constructs
    the graph data structure.  For example, the 13-node graph from
    Sedgewick, figure 32.1 can be created as follows:
<PRE>
    make_graph( 13,
	[ e(1,6,1),e(1,2,1),e(1,7,1),e(3,1,1),e(4,6,1),e(5,4,1),
	  e(6,5,1),e(7,5,1),e(7,10,1),e(7,3,1),e(8,7,1),e(8,9,1),e(9,8,1),
	  e(10,11,1),e(10,12,1),e(10,13,1),e(12,7,1),e(12,13,1),e(13,12,1) ],
        Graph).
</PRE>
    Often, the nodes have names or other information attached.
    This can be added to the Graph using graph_set_nodenames/2 which
    takes an existing graph and adds an array of node information
    (usually the node names, but any ground term can be used).
    For the Sedgewick-graph above, we could invoke
<PRE>
    graph_set_nodenames(Graph, [](a,b,c,d,e,f,g,h,i,j,k,l,m))
</PRE>
    If nodes have names anyway, it can be more convenient to specify
    the edges in terms of these node names rather than node numbers.
    Such symbolic edges are written in the form
<PRE>
	edge(SourceName, TargetName, EdgeData)
</PRE>
    where SourceName and TargetName should match an entry (usually the
    node name) in the graph's nodename-array.  A graph can now be
    constructed by giving a nodename-array and a list of symbolic edges
    to make_graph_symbolic/3, e.g. to build the same graph as above, use
<PRE>
    make_graph_symbolic(
	[](a,b,c,d,e,f,g,h,i,j,k,l,m),
	[ edge(a,f,1),edge(a,b,1),edge(a,g,1),edge(c,a,1),edge(d,f,1),edge(e,d,1),
	  edge(f,e,1),edge(g,e,1),edge(g,j,1),edge(g,c,1),edge(h,g,1),edge(h,i,1),edge(i,h,1),
	  edge(j,k,1),edge(j,l,1),edge(j,m,1),edge(l,g,1),edge(l,m,1),edge(m,l,1) ],
	Graph).
</PRE>
    Note the use of the functor e/3 for the internal edge representation
    and edge/3 for the symbolic edge representation.
</P><P>
    There is no special data structure for undirected graphs - they can
    be represented by having reverse edges corresponding to every edge.
    It is allowed to have parallel edges (more than one edge from S to T)
    as long as their EdgeData fields differ.
<H4>Visualization</H4>
    You can use library(graphviz) or lib(viewable) to draw these graphs.
<H4>Overview of Shortest-Path Functionality</H4>
    This library provides a number of different variants of shortest path
    algorithms, of which the following table gives an overview:
<TABLE BORDER="1">
<TR>
<TH>Predicate</TH>
    <TH>Sinks</TH>
    <TH>Paths</TH>
    <TH>Determinism</TH>
    <TH>Edge Weights</TH>
    <TH>Tolerance</TH>
</TR>
<TR>
<TD>shortest_paths/4</TD>
    <TH>all</TH>
    <TH>one</TH>
    <TH>det</TH>
    <TH>non-negative</TH>
    <TH>no</TH>
</TR>
<TR>
<TD>shortest_paths_bellman_ford/4</TD>
    <TH>all</TH>
    <TH>one</TH>
    <TH>det</TH>
    <TH>arbitrary</TH>
    <TH>no</TH>
</TR>
<TR>
<TD>all_short_paths_as_graph/6</TD>
    <TH>all</TH>
    <TH>all</TH>
    <TH>det</TH>
    <TH>non-negative</TH>
    <TH>yes</TH>
</TR>
<TR>
<TD>all_short_paths_as_edges/6 + possible_path/7</TD>
    <TH>all</TH>
    <TH>all</TH>
    <TH>nondet</TH>
    <TH>non-negative</TH>
    <TH>yes</TH>
</TR>
<TR>
<TD>incremental_all_shortest_paths_as_graph/6</TD>
    <TH>all</TH>
    <TH>all</TH>
    <TH>det</TH>
    <TH>positive</TH>
    <TH>no</TH>
</TR>
<TR>
<TD>incremental_all_shortest_paths_as_edges/6 + possible_path/7</TD>
    <TH>all</TH>
    <TH>all</TH>
    <TH>nondet</TH>
    <TH>positive</TH>
    <TH>no</TH>
</TR>
<TR>
<TD>single_pair_shortest_path/5</TD>
    <TH>single</TH>
    <TH>one</TH>
    <TH>semidet</TH>
    <TH>non-negative</TH>
    <TH>no</TH>
</TR>
<TR>
<TD>single_pair_shortest_path_bellman_ford/5</TD>
    <TH>single</TH>
    <TH>one</TH>
    <TH>semidet</TH>
    <TH>arbitrary</TH>
    <TH>no</TH>
</TR>
<TR>
<TD>single_pair_all_short_paths_as_graph/7</TD>
    <TH>single</TH>
    <TH>all</TH>
    <TH>det</TH>
    <TH>non-negative</TH>
    <TH>yes</TH>
</TR>
<TR>
<TD>single_pair_short_path/6</TD>
    <TH>single</TH>
    <TH>all</TH>
    <TH>nondet</TH>
    <TH>non-negative</TH>
    <TH>yes</TH>
</TR>
<TR>
<TD>incremental_single_pair_all_shortest_paths_as_graph/7</TD>
    <TH>single</TH>
    <TH>all</TH>
    <TH>det</TH>
    <TH>positive</TH>
    <TH>no</TH>
</TR>
<TR>
<TD>incremental_single_pair_shortest_path/6</TD>
    <TH>single</TH>
    <TH>all</TH>
    <TH>nondet</TH>
    <TH>positive</TH>
    <TH>no</TH>
</TR>
</TABLE>

<H4>To-do list</H4>
    The following operations should be added:
<UL>
    <LI>Graph modification: adding, removing, projecting
    <LI>Matching
    <LI>Flow
    ...
</UL>
</P>
<H2>About</H2><UL COMPACT>
<LI><STRONG>Author: </STRONG>Joachim Schimpf
<LI><STRONG>Copyright &copy; </STRONG>Cisco Systems, Inc.
<LI><STRONG>Date: </STRONG>$Date: 2009/02/19 05:45:20 $
</UL>
<HR>Generated from graph_algorithms.eci on 2009-05-27 01:25
</BODY></HTML>
